package com.my.algorithmlearning.leetcode;

import org.apache.commons.lang3.StringUtils;
import org.springframework.util.Assert;

/**
 * @ClassName Medium_31_NextPermutation
 * @Description Medium_31_NextPermutation
 * @Author wanghaiwei
 * @Date 2023/2/8 10:37
 */
public class Medium_31_NextPermutation {

    public void nextPermutation(int[] nums) {
        if (nums.length <= 1) {
            return;
        }
        //记录第一个下降点
        int firstSlumpIdx = nums.length - 2;
        //记录最后一个上升点
        int lastClimbIdx = nums.length - 1;
        while (firstSlumpIdx >= 0 && nums[firstSlumpIdx] >= nums[lastClimbIdx]) {
            //注意如果firstSlumbIdx==0的时候，仍然会进来执行一次，导致firstSlumpIdx=-1，lastClimbIdx=0，意味着，当前整个排列就是自然降序的
            firstSlumpIdx--;
            lastClimbIdx--;
        }
        //lastClimbIdx=0，意味着，当前整个排列就是自然降序的，只需要逆序就是答案了
        if (lastClimbIdx == 0) {
            this.revertArrayInPlace(nums, 0, nums.length - 1);
            return;
        }
        //从尾部到lastClimbIdx位置，找到第一个大于nums[firstSlumpIdx]的值，与nums[firstSlumpIdx]交换
        int exchangeIdx = nums.length - 1;
        while (exchangeIdx >= lastClimbIdx && nums[exchangeIdx] <= nums[firstSlumpIdx]) {
            exchangeIdx--;
        }
        //交换exchangeIdx和firstSlumpIdx的值
        int tmp = nums[exchangeIdx];
        nums[exchangeIdx] = nums[firstSlumpIdx];
        nums[firstSlumpIdx] = tmp;
        //最后，将lastClimbIdx逆序即可
        this.revertArrayInPlace(nums, lastClimbIdx, nums.length - 1);
    }

    private void revertArrayInPlace(int[] nums, int beginIdxInclude, int endIdxInclude) {
        for (int i = beginIdxInclude, j = endIdxInclude; i < j; i++, j--) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

    public static void main(String[] args) {
        Medium_31_NextPermutation solution = new Medium_31_NextPermutation();
        int[] nums = new int[]{1, 2, 3};
        solution.nextPermutation(nums);
        Assert.isTrue("1,3,2".equals(StringUtils.join(nums, ',')), "nums = [1,2,3]计算错误，预期：[1,3,2]，实际：" + StringUtils.join(nums, ','));

        nums = new int[]{1, 2, 4, 6, 5};
        solution.nextPermutation(nums);
        Assert.isTrue("1,2,5,4,6".equals(StringUtils.join(nums, ',')), "nums = [1,2,4,6,5]计算错误，预期：[1,2,5,4,6]，实际：" + StringUtils.join(nums, ','));
    }
}
